Séminaire Lotharingien de Combinatoire, 78B.6 (2017), 9 pp.
Alexander Diaz-Lopez, Pamela E. Harris,
Erik Insko and Mohamed Omar
A Proof of the Peak Polynomial Positivity Conjecture
Abstract.
We say that a permutation
π=π1π2...πn in
Sn has a peak at index i if
πi-1 < πi >
πi+1. Let
P(π) denote the set of indices where π has
a peak. Given a set S of positive integers, we define
P(S;n) =
{π in Sn : P(π)=S}.
In 2013 Billey, Burdzy,
and Sagan showed that for subsets of positive integers S and
sufficiently large n,
|P(S;n)|
= pS(n)2n-|S|-1
where pS(x)
is a polynomial depending on S. They gave a recursive formula for
pS(x)
involving an alternating sum, and they conjectured that the
coefficients of pS(x)
expanded in a binomial coefficient basis
centered at max(S) are all nonnegative. In this paper we
introduce a new recursive formula for
|P(S;n)| without alternating
sums and we use this recursion to prove that their conjecture is
true.
Received: November 14, 2016.
Accepted: February 17, 2017.
Final version: April 1, 2017.
The following versions are available: